Parity problem (sieve theory)

In number theory, the parity problem refers to a limitation in sieve theory that prevents sieves from giving good estimates in many kinds of prime-counting problems. The problem was identified and named by Atle Selberg in 1949. Beginning around 1996, John Friedlander and Henryk Iwaniec developed some parity-sensitive sieves that make the parity problem less of an obstacle.

Contents

The problem

Terence Tao gave this "rough" statement of the problem:[1]

Parity problem. If A is a set whose elements are all products of an odd number of primes (or are all products of an even number of primes), then (without injecting additional ingredients), sieve theory is unable to provide non-trivial lower bounds on the size of A. Also, any upper bounds must be off from the truth by a factor of 2 or more.

This problem is significant because it may explain why it is difficult for sieves to "detect primes," in other words to give a non-trivial lower bound for the number of primes with some property. For example, in a sense Chen's theorem is very close to a solution of the twin prime conjecture, since it says that there are infinitely many primes such that prime + 2 is either prime or the product of two primes. The parity problem suggests that, because the case of interest has an odd number of prime factors (namely 1), it won't be possible to separate out the two cases using sieves.

Example of the parity problem

This example is due to Selberg and is given as an exercise with hints by Cojocaru & Murty.[2]:133–134

The problem is to estimate separately the number of numbers ≤ x with no prime divisors ≤ x1/2, that have an even (or an odd) number of prime factors. It can be shown that, no matter what the choice of weights in a Brun- or Selberg-type sieve, the upper bound obtained will be at least (2 + o(1)) x / ln x for both problems. But in fact the set with an even number of factors is empty and so has size 0. The set with an odd number of factors is just the primes between x1/2 and x, so by the prime number theorem its size is (1 + o(1)) x / ln x. Thus these sieve methods are unable to give a useful upper bound for the first set, and overestimate the upper bound on the second set by a factor of 2.

Parity-sensitive sieves

Beginning around 1996 John Friedlander and Henryk Iwaniec developed some new sieve techniques to "break" the parity problem.[3][4] One of the triumphs of these new methods is the Friedlander–Iwaniec theorem, which states that there are infinitely many primes of the form a2 + b4.

Notes

  1. ^ Tao, Terence (2007-06-05). "Open question: The parity problem in sieve theory". http://terrytao.wordpress.com/2007/06/05/open-question-the-parity-problem-in-sieve-theory/. Retrieved 2008-08-11. 
  2. ^ Cojocaru, Alina Carmen; M. Ram Murty (2005). An introduction to sieve methods and their applications. London Mathematical Society Student Texts. 66. Cambridge University Press. ISBN 0-521-61275-6. 
  3. ^ Friedlander, John; Henryk Iwaniec (1997-02-18). "Using a parity-sensitive sieve to count prime values of a polynomial". Proceedings of the National Academy of Sciences 94. doi:10.1073/pnas.94.4.1054. PMC 19742. PMID 11038598. 1054–1058. http://www.pnas.org/content/94/4.toc. Retrieved 2008-08-11. 
  4. ^ Friedlander, John; Henryk Iwaniec (1998). "Asymptotic sieve for primes". Annals of Mathematics (Annals of Mathematics) 148 (3): 1041–1065. arXiv:math/9811186. doi:10.2307/121035. JSTOR 121035.